Exercici 7 (Tasca 4).
(membership problem,
context-free languages,
CKY algorithm,
decidable properties)
La pertinença a un incontextual és decidible en temps polinòmic
Considereu el problema decisional següent:
\mathtt{Pertinen\c{c}a_{CFL}}: \text{ donada una entrada $x\in \{0,1\}^*$ i una CFG $G$, determinar si } x\in L(G).
Demostreu que \mathtt{Pertinen\c{c}a_{CFL}} es pot decidir en temps polinòmic respecte de |x| i la mida de G. Feu-ho explicant com funciona l’algorisme Cocke-Kasami-Younger (CKY).
Precaució
L’algorisme CKY assumeix que l’entrada és una gramàtica en forma normal de Chomsky.